22.7 KB · ⇊ 7 parts · ⤓ Micron 22.7 KB · ⤓ HTML 118.5 KB

layout: Wide · Narrow · Centered

top

Le code de Reed-Solomon est un code correcteur basé sur les corps finis dont le principe est de construire un polynôme formel à partir des symboles à transmettre et de le suréchantillonner. Le résultat est alors envoyé, au lieu des symboles originaux. La redondance de ce suréchantillonnage permet au récepteur du message codé de reconstruire le polynôme même s'il y a eu des erreurs pendant la transmission.

• Histoire

• Vue d'ensemble

• Un exemple de code de Reed-Solomon

• L'information à transmettre

• Le codage

• La transmission du message

• La correction des erreurs

• Les erreurs d'effacement

• Applications

• Stockage de données

• Transmission par satellite

• Transmission de données

• Code QR

• Exemple

• Faiblesse

• Utilisation dans un modem avec codeur convolutif

• Liens externes

• Références

Ce code est dû à Irving S. Reed et Gustave Solomoncite-ref-1[1]. Il a notamment été utilisé pour le codage des CDscite-ref-boyer-2-0[2].

Soient m, n, k, t des nombres entiers strictement positifs tels que n = 2 m − 1 = k + 2 t {\displaystyle n=2^{m}-1=k+2t} . Généralement, on prend m = 8 (parfois m = 16), n = 255, k = 239, t = 8. Les codes Reed-Solomon sont des codes par bloc. En effet ils prennent en entrée un bloc de données de taille fixée k, chaque donnée étant un symbole élément du corps fini possédant 2 m {\displaystyle 2^{m}} éléments. On ajoute à ce bloc 2t symboles de contrôle, formant ainsi un bloc de sortie de taille fixée égale à n. Ainsi, on a :

• m : nombre de bits par symbole. Dans le cas où m = 8, les symboles sont des octets.

• k : nombre de symboles d’information, appelé charge utile ;

• 2t : nombre de symboles de contrôle ou de redondance ;

• n: nombre de symboles transmis (charge utile et contrôle).

Grâce à l'ajout des symboles de contrôle, ces codes permettent de corriger deux types d'erreurs :

• les erreurs induisant une modification des données, où certains bits passent de la valeur 0 à la valeur 1 et vice versa comme sur le canal binaire symétrique ;

• les erreurs provoquant des pertes d'informations aussi appelées effacements, lorsque des paquets d'informations sont perdus ou effacés comme sur le canal binaire à effacement.

On note un codage de Reed-Solomon R S ( n , k ) {\displaystyle RS(n,k)} ou R S ( n , k , t ) {\displaystyle RS(n,k,t)} .

Si la localisation des erreurs n'est pas connue à l'avance — ce qui est le cas en pratique — le codage Reed-Solomon sait corriger t erreurs.

n étant souvent trop important en pratique, une partie des informations peut être remplacée par des zéros avant codage et ne sera pas transmise, mais devra être ajoutée avant décodage. On parle dans ce cas de code Reed-Solomon raccourci (« shortened Reed-Solomon codes »).

On peut également concevoir des codes de Reed-Solomon sur des corps finis quelconques.

Il existe plusieurs variantescite-ref-4[4]cite-ref-5[5]cite-ref-6[6] du code de Reed-Solomon, développées au cours des dernières décennies dans le but de rendre de plus en plus rapides les procédés de codage et de décodage. Une des variantes possibles est présentée ici.

Soit un message A constitué de k symboles éléments du corps fini F 2 m {\displaystyle \mathbb {F} _{2^{m}}} . Ce corps est de caractéristique 2, ce qui signifie qu'il satisfait à la règle de calcul 1 + 1 = 0, ou encore 1 = -1, ou encore qu'il n'y a pas de distinction entre somme et différence. Il possède par ailleurs un élément dit primitif α {\displaystyle \alpha } ayant la propriété suivante :

• Les éléments ( 1 , α , α 2 , . . . , α m − 1 ) {\displaystyle (1,\alpha ,\alpha ^{2},...,\alpha ^{m-1})} forment une base de F 2 m {\displaystyle \mathbb {F} _{2^{m}}} en tant qu'espace vectoriel de dimension m sur le corps F 2 {\displaystyle \mathbb {F} _{2}} .

• α {\displaystyle \alpha } engendre le groupe multiplicatif de F 2 m {\displaystyle \mathbb {F} _{2^{m}}}

Ainsi, les éléments non nuls de F 2 m {\displaystyle \mathbb {F} _{2^{m}}} peuvent s'écrire comme combinaisons linéaires de ( 1 , α , α 2 , . . . , α m − 1 ) {\displaystyle (1,\alpha ,\alpha ^{2},...,\alpha ^{m-1})} à coefficients dans {0,1}, mais aussi comme une puissance de α {\displaystyle \alpha } , entre 0 et 2 m − 2 {\displaystyle 2^{m}-2} .

Les k symboles constituant le message A sont considérés comme les coefficients d'un polynôme de degré inférieur ou égal à k-1, i.e. un élément de F 2 m [ X ] {\displaystyle \mathbb {F} _{2^{m}}[X]} . Ce polynôme est l'information à transmettre et sera encore noté A {\displaystyle A} .

On appelle polynôme générateur le polynôme G {\displaystyle G} de degré 2t défini de la façon suivante :

G ( X ) = ( X + α ) ( X + α 2 ) … ( X + α 2 t ) {\displaystyle G(X)=(X+\alpha )(X+\alpha ^{2})\dots (X+\alpha ^{2t})}

Ce polynôme admet pour racines les α i , 1 ≤ i ≤ 2 t {\displaystyle \alpha ^{i},1\leq i\leq 2t} .

On définit le polynôme de contrôle B {\displaystyle B} comme étant le reste de la division euclidienne de A × X 2 t {\displaystyle A\times X^{2t}} par G . {\displaystyle G.} Ce polynôme est de degré strictement inférieur à 2t. Les coefficients de ce polynôme forment le code de contrôle de l'information A.

On définit alors le polynôme C = A × X 2 t + B {\displaystyle C=A\times X^{2t}+B} . Ce polynôme est de degré inférieur ou égal à k − 1 + 2 t = n − 1 {\displaystyle k-1+2t=n-1} . Il possède la propriété de s'annuler en α i , 1 ≤ i ≤ 2 t {\displaystyle \alpha ^{i},1\leq i\leq 2t} . (rappel : on est toujours dans un corps de caractéristique 2, donc + et - ont le même effet)

Les coefficients du polynôme C {\displaystyle C} sont transmis au destinataire. Au cours de cette transmission, des erreurs portant sur certains coefficients peuvent se produire, et le destinataire reçoit des coefficients formant un polynôme D {\displaystyle D} .

Le destinataire teste alors si, pour tout i entre 1 et 2t, on a bien D ( α i ) = 0 {\displaystyle D(\alpha ^{i})=0} . Si c'est le cas, il considère qu'il n'y a eu aucune erreur de transmission et que D = C {\displaystyle D=C} . Il retrouve l'information A dans les k-1 coefficients des termes de degrés les plus élevés du polynôme D {\displaystyle D} .

Si au moins l'un des D ( α i ) {\displaystyle D(\alpha ^{i})} est non nul, il y a eu erreur de transmission sur au moins l'un des coefficients. Cependant, le destinataire considère que le nombre de coefficients affectés est inférieur ou égal à t. Sous cette hypothèse, il va être capable de reconstituer le message C initial.

Si D {\displaystyle D} est différent de C {\displaystyle C} , soit E = D + C {\displaystyle E=D+C} , polynôme de degré inférieur ou égal à n-1, et comportant un nombre ν {\displaystyle \nu } de coefficients non nuls. Par hypothèse, on suppose que ν {\displaystyle \nu } est inférieur ou égal à t. Posons :

E = ∑ r = 1 ν e i r X i r {\displaystyle E=\sum _{r=1}^{\nu }e_{i_{r}}X^{i_{r}}} , y r = e i r {\displaystyle y_{r}=e_{i_{r}}} et x r = α i r {\displaystyle x_{r}=\alpha ^{i_{r}}} , les i r {\displaystyle i_{r}} étant des indices distincts pouvant varier entre 0 et n-1.

E {\displaystyle E} est pour le moment inconnu du destinataire. Il s'agit pour celui-ci de déterminer :

Le nombre d'erreurs ν {\displaystyle \nu } ,

les rangs i r {\displaystyle i_{r}} où sont situées ces erreurs,

les valeurs y r {\displaystyle y_{r}} de ces erreurs.

Une fois ces informations reconstituées, le destinataire sera en mesure de déterminer le polynôme E {\displaystyle E} et de reconstituer le message initial C = D + E {\displaystyle C=D+E} . Pour cela, on suit les cinq étapes suivantes.

1) Calcul des syndromes : On calcule les 2t quantités S j = D ( α j ) , 1 ≤ j ≤ 2 t {\displaystyle S_{j}=D(\alpha ^{j}),1\leq j\leq 2t} , appelées syndromes. Comme E = D + C {\displaystyle E=D+C} et que les C ( α j ) {\displaystyle C(\alpha ^{j})} sont nuls, on a également :

S j = E ( α j ) = ∑ r = 1 ν e i r ( α j ) i r = ∑ r = 1 ν e i r ( α i r ) j = ∑ r = 1 ν y r ( x r ) j {\displaystyle S_{j}=E(\alpha ^{j})=\sum _{r=1}^{\nu }e_{i_{r}}({\alpha ^{j}})^{i_{r}}=\sum _{r=1}^{\nu }e_{i_{r}}({\alpha ^{i_{r}}})^{j}=\sum _{r=1}^{\nu }y_{r}(x_{r})^{j}}

On dispose ainsi de 2t équations dont les inconnues x r {\displaystyle x_{r}} et y r {\displaystyle y_{r}} sont au plus au nombre de 2t. Cependant, le système n'est pas linéaire et sa résolution est technique.

2) Détermination du nombre d'erreurs : On considère le polynôme Λ ( X ) = ∏ r = 1 ν ( 1 − x r X ) {\displaystyle \Lambda (X)=\prod _{r=1}^{\nu }(1-x_{r}X)} dont les racines sont les inverses des x r {\displaystyle x_{r}} . Ce polynôme se développe sous la forme Λ ( X ) = 1 + λ 1 X + λ 2 X 2 + ⋯ + λ ν X ν {\displaystyle \Lambda (X)=1+\lambda _{1}X+\lambda _{2}X^{2}+\dots +\lambda _{\nu }X^{\nu }} . On peut vérifier que les ν {\displaystyle \nu } coefficients λ r {\displaystyle \lambda _{r}} , inconnus du destinataire, satisfont un système linéaire de ν {\displaystyle \nu } équations, la j-ème équation étant, pour j variant de 1 à ν {\displaystyle \nu } :

S ν + j − 1 λ 1 + S ν + j − 2 λ 2 + ⋯ + S j λ ν = − S ν + j {\displaystyle S_{\nu +j-1}\lambda _{1}+S_{\nu +j-2}\lambda _{2}+\dots +S_{j}\lambda _{\nu }=-S_{\nu +j}}

en effet : ( ∑ i = 1 ν S ν + j − i λ i = ∑ r = 1 ν y r ( ∑ i = 1 ν x r ν + j − i λ i ) = ∑ r = 1 ν y r x r ν + j ( Λ ( x r − 1 ) − 1 ) = − S ν + j ) {\displaystyle \left(\sum _{i=1}^{\nu }S_{\nu +j-i}\lambda _{i}=\sum _{r=1}^{\nu }y_{r}(\sum _{i=1}^{\nu }x_{r}^{\nu +j-i}\lambda _{i})=\sum _{r=1}^{\nu }y_{r}x_{r}^{\nu +j}(\Lambda (x_{r}^{-1})-1)=-S_{\nu +j}\right)}

De plus, la plus grande valeur ν {\displaystyle \nu } inférieure ou égal à t pour laquelle le déterminant de ce système est non nul est précisément le nombre ν {\displaystyle \nu } égal au nombre d'erreurs transmises. On part donc de ν = t {\displaystyle \nu =t} , et si le déterminant est nul, on décrémente ν {\displaystyle \nu } jusqu'à obtenir un déterminant non nul.

3) Détermination de l'emplacement des erreurs : Une fois ν {\displaystyle \nu } ainsi déterminé, on résout le système, ce qui définit le polynôme Λ {\displaystyle \Lambda } . On cherche les racines de ce polynôme, dont les inverses donnent les valeurs des x r {\displaystyle x_{r}} . Pour chaque r entre 1 et ν {\displaystyle \nu } , on cherche la puissance i r {\displaystyle i_{r}} de α {\displaystyle \alpha } telle que x r = α i r {\displaystyle x_{r}=\alpha ^{i_{r}}} . On a ainsi déterminé les rangs i r {\displaystyle i_{r}} des erreurs transmises.

4) Détermination de la valeur des erreurs : Les x r {\displaystyle x_{r}} étant désormais connus, on peut résoudre le système dont l'équation générale est S j = ∑ r = 1 ν y r x r j {\displaystyle S_{j}=\sum _{r=1}^{\nu }y_{r}x_{r}^{j}} et dont les inconnues sont les y r {\displaystyle y_{r}} , permettant de déterminer les valeurs de ces inconnues. Ce sont les valeurs des erreurs commises.

5) Correction du message reçu : Connaissant les i r {\displaystyle i_{r}} et les y r {\displaystyle y_{r}} , on connaît le polynôme E , {\displaystyle E,} et donc le message initial C = D + E {\displaystyle C=D+E}

Si l'information est inscrite sur un support comme un CD ou un DVD, il peut se produire des erreurs d'effacement. L'erreur est précisément localisée mais on ne peut lire aucune information à cet endroit. On peut cependant reconstituer les symboles effacés en s'aidant là aussi des équations données par les syndromes. Comme les localisations x r {\displaystyle x_{r}} sont connues, que les inconnues sont les seules valeurs y r {\displaystyle y_{r}} et qu'on dispose de 2t équations, on peut corriger l'effacement de ν = 2 t {\displaystyle \nu =2t} symboles.

Pour le CD, on utilise 2 codages de Reed-Solomon (code CIRC pour Cross Interleaved Reed-Solomon Code). On code une première fois avec un code C1 = RS(28, 24), puis on entrelace (ceci permet de répartir l'information afin de mieux résister aux trains d'erreurs consécutives que peut provoquer une rayure qui détruit beaucoup d'octets localement), ensuite on code à nouveau les données entrelacées avec un code C2 = RS(32, 28). L'idée est que le premier code permet d'éliminer le bruit ambiant mais s'il ne peut corriger (par exemple, s'il y a une salve d'erreurs), il efface le bloc (car on peut corriger deux fois plus d'effacements que de caractères faux) et ensuite le code est désentrelacé. Ainsi la perte d'information est diluée sur une grande plage de données ce qui permet au code de corriger ces effacements.

Pour le DVD le principe est le même que pour les CD, on a un code PI= RS(182, 172) et un code PO = RS(208, 192)

Pour le DVB, le codage est RS(204, 188, t=8)

En ADSL/ADSL2/ADSL2plus, le codage est souvent RS(240, 224, t=8) ou encore RS(255, 239, t=8).

Le code Reed-Solomon est utilisé dans les QR code, la correction d'erreur permettant de lire le QR code même si celui-ci est sali ou abimécite-ref-7[7].

pour le DVB, le codage est RS(204, 188, t=8)

Pour 188 (=k) octets en entrée, on ajoute 16(=2 t) octets de correction d'erreur, ce qui donne 204 en sortie du codeur.

8 octets (=t) sur 204 peuvent être corrigés.

Si plus de 8 octets sont détectés comme erronés, le bloc de données utiles est marqué comme défectueux. Aucune erreur n'est alors corrigée

En raison du faible nombre de symboles que le codage Reed-Solomon peut corriger, ce codage est très mauvais en cas de bruit impulsif de longue durée, ou de bruit aléatoire régulier.

• Pour la transmission de données (ADSL, DVB-T), le bruit impulsif peut être dû à des moteurs, relais, lampes à décharge ou tubes d'éclairage, clôture électrique...

• Pour le stockage de données (CD, DVD), le bruit impulsif peut être dû à une rayure sur le support.

En général, en émission, dans un modem (ADSL, modem satellite IDR/SMS, DVB-S, etc ), le codage Reed-Solomon, renforcé par un entrelaceur est accompagné d'un codeur convolutif. En réception, les erreurs résiduelles non corrigées par le décodeur de Viterbi seront alors désentrelacées dans les blocs d'origines et corrigées par le décodeur Reed-Solomon dans la mesure de son pouvoir correcteur.

Le but du désentrelaceur est de remplacer en réception, une salve d'erreurs regroupées et souvent non corrigeables (bruit impulsif) par une multitude d'erreurs réparties et souvent corrigeables pour le décodeur de Reed-Solomon.

• Code Reed-Solomon Principes et programmation du code Reed-Solomon en Java.

• William Geisel, Tutorial on Reed–Solomon Error Correction Coding, NASA, Technical Memorandum (1990)

cite-note-11. ↑ reed-g-solomon1960i-s-reed-g-solomon1960(en) I. S. Reed, G. Solomon, « Polynomial codes over certain finite fields », J. Soc. Indus. Appl. Math., no 8,‎ 1960, p. 300-304

cite-note-boyer-22. ↑ boyer2019pascal-boyer2019Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 8.4 (« Codes BCH »), p. 560-562.

cite-note-31. (en) « NASA Beams Mona Lisa to Lunar Reconnaissance Orbiter at the Moon », sur nasa.gov

cite-note-44. ↑ gorenstein-n-ziegler1961d-gorenstein-n-ziegler1961(en) D. Gorenstein, N. Ziegler, « D class of error-correcting codes in p m {\displaystyle p^{m}} symbols », J. Soc. Indus. Math. Appl., no 9,‎ 1961, p. 207-2014

cite-note-55. ↑ peterson1960w-w-peterson1960(en) W. W. Peterson, « Encoding and error-correction procedures for the Bose-Chaudhuri codes », IRE Trans. Inform. Theory, no IT-6,‎ 1960, p. 459-470

cite-note-66. ↑ bras-amoros2018maria-bras-amoros2018(en) Maria Bras-Amoros, « A decoding approach to Reed-Solomon codes from their definition », Amer. Math. Monthly, vol. 125, no 4,‎ avril 2018, p. 320-338

cite-note-77. ↑ tiwari2016sumit-tiwari2016Sumit Tiwari, « An Introduction to QR Code Technology », 2016 International Conference on Information Technology, IEEE,‎ décembre 2016, p. 39–44 (ISBN 978-1-5090-3584-7, DOI 10.1109/ICIT.2016.021, lire en ligne, consulté le 28 octobre 2024)

• Portail des mathématiques

• Portail des télécommunications

• Portail de l'informatique théorique